public class QuickSortHero {
    public static void main(String[] args) {
//        int[] arr = {6,5,7,3,9,8,5,2,10,4};
        int[] arr = {5,5,6,5};
        sortArray(arr);
        for (int n : arr) {
            System.out.println(n);
        }
    }

    public static int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }

    private static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(nums, left, right);
        quickSort(nums,left,pivot);
        quickSort(nums,pivot+1,right);
    }

    private static int partition(int[] nums, int low, int high) {
        int pivot = nums[low];
        int left = low-1;
        int right = high+1;
        while (true) {
            do {
                right--;
            } while (nums[right] > pivot);
            do {
                left++;
            } while (nums[left] < pivot);
            if (left >= right) {
                return right;
            }
            swap(nums, left, right);
        }
    }

    private static void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}
